home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / prolog_2.zip / PUZZLES.ZIP / RIVER.PRO < prev    next >
Text File  |  1986-07-20  |  6KB  |  131 lines
  1.      /*             Farmer-goat-wolf-cabbage problem
  2.  
  3.      The Prolog code below solves the farmer-goat-wolf-cabbage
  4.      problem.
  5.      The problem details are as follows:
  6.  
  7.           1.   A farmer is on one side of a river with a goat,
  8.                wolf, and cabbage.  A boat is at his disposal
  9.                to get himself and his companions/baggage
  10.                to the other side.
  11.  
  12.           2.   Only the farmer can row the boat, either alone
  13.                or with one passenger.
  14.  
  15.           3.   The following pairs cannot co-exist without the
  16.                stabilizing presence of the farmer:
  17.  
  18.                a.   wolf and goat - wolf will eat the goat
  19.  
  20.                b.   goat and cabbage - goat will eat the cabbage
  21.  
  22.      The following predicates have been coded to solve the problem.
  23.  
  24.                predicate                     description
  25.                *********           *********************************
  26.  
  27.                solvex              the 'main' predicate, highest level
  28.                                    problem solving call
  29.  
  30.                move                generates a move for the game
  31.  
  32.                member              tests a state to see if it has been used
  33.                                    before, i.e., prevents a logical loop.
  34.  
  35.                badx                lists the bad, or disallowed, states.
  36.  
  37.                prt                 prints the problem solution, or the states
  38.                                    traversed.
  39.  
  40.      The following statement initiates the problem solving process:
  41.  
  42.                solvex(statex(south,south,south,south),[],[]).
  43.  
  44.      This statement says that the farmer, goat, wolf, and cabbage
  45.      (respectively) are on the south side of the river (the starting
  46.      state for the game) and that the solution and print lists are
  47.      initially empty.
  48. .PA
  49.      The solvex rules are given below.  The rule immediately below must
  50.      come first.                                                      */
  51.  
  52.      solvex(statex(north,north,north,north),Solution_list,Print_list) :-
  53.                     prt(Print_list),!.
  54.  
  55.      /* This statement (above) terminates the program when everybody
  56.         is on the north side of the river and generates a listing of the
  57.         solution.
  58.  
  59.         The statement below adds the initial state on the solution and
  60.         print lists, generates the first move, tests the move for correctness,
  61.         stores that move on the solution and print lists, and calls
  62.         solvex to generate the next move in the game.                */
  63.  
  64.      solvex(statex(south,south,south,south),[],[]) :-
  65.           move(Mtype,statex(south,south,south,south),
  66.                      statex(Mf1,Mw1,Mg1,Mc1)),
  67.           not(badx(statex(Mf1,Mw1,Mg1,Mc1))),
  68.           solvex(statex(Mf1,Mw1,Mg1,Mc1),
  69.                          [[Mf1,Mw1,Mg1,Mc1],
  70.                           [south,south,south,south]],
  71.                          [[Mtype,Mf1,Mw1,Mg1,Mc1],
  72.                           [start,south,south,south,south]]).
  73.  
  74.      /*   The next statement/predicate does most of the work.  It takes the
  75.           input state, generates another state, i.e., a move in the game,
  76.           checks to see if it is a legal move, checks to see if that state
  77.           has been used before (to prevent a loop, or circular reasoning),
  78.           saves the state on both the solution and print lists, and
  79.           calls itself recursively to generate yet another move.      */
  80.  
  81.      solvex(statex(Mfarmer,Mwolf,Mgoat,Mcabbage),Solution_list,Print_list) :-
  82.           move(Mtype,statex(Mfarmer,Mwolf,Mgoat,Mcabbage),
  83.                      statex(Mf1,Mw1,Mg1,Mc1)),
  84.           not(badx(statex(Mf1,Mw1,Mg1,Mc1))),
  85.           not(member([Mf1,Mw1,Mg1,Mc1],Solution_list)),
  86.           solvex(statex(Mf1,Mw1,Mg1,Mc1),
  87.                [[Mf1,Mw1,Mg1,Mc1]|Solution_list],
  88.                [[Mtype,Mf1,Mw1,Mg1,Mc1]|Print_list]).
  89.  
  90. /*          The bad, or disallowed states are listed below       */
  91.  
  92.      badx(statex(north,south,south,_)).  /* wolf and goat on south side*/
  93.  
  94.      badx(statex(south,north,north,_)).  /* wolf and goat on north side*/
  95.  
  96.      badx(statex(north,_,south,south)).  /* goat and cabbage on south */
  97.  
  98.      badx(statex(south,_,north,north)).  /* goat and cabbage on north */
  99. /*
  100. .PA
  101.           The legal moves are described below.  The fact that we have
  102.           described the disallowed states above allows the use of variables
  103.           in the description below rather than spelling out all of the legal
  104.           moves in excrutiating detail.
  105.  
  106.           These moves have been ordered to produce one solution as fast as
  107.           possible.  The eventual success of the program does not depend on
  108.           the ordering although different solutions may result with other
  109.           orderings.                                                  */
  110.  
  111.      move(goat,statex(south,Mz,south,Ma),statex(north,Mz,north,Ma)).
  112.      move(farmer,statex(south,Mx,Ma,Mb),statex(north,Mx,Ma,Mb)).
  113.      move(wolf,statex(south,south,Mz,Ma),statex(north,north,Mz,Ma)).
  114.      move(goat,statex(north,Mz,north,Ma),statex(south,Mz,south,Ma)).
  115.      move(cabbage,statex(south,Mz,Ma,south),statex(north,Mz,Ma,north)).
  116.      move(farmer,statex(north,Mz,Ma,Mb),statex(south,Mz,Ma,Mb)).
  117.      move(wolf,statex(north,north,Mz,Ma),statex(south,south,Mz,Ma)).
  118.      move(cabbage,statex(north,Mz,Ma,north),statex(south,Mz,Ma,south)).
  119.  
  120.      /* The member predicate definition                               */
  121.  
  122.      member(X,[X|_]).
  123.      member(X,[_|L]) :- member(X,L).
  124.  
  125.      /* Predicate to print the final result                           */
  126.  
  127.      prt([]) :- nl.
  128.      prt([X|L]) :- write(X),nl,prt(L).
  129.  
  130.      /*   That's all folks                                            */
  131.